package me.mingshan.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/remove-duplicate-letters/description/
 *
 * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "bcabc"
 * 输出："abc"
 * 示例 2：
 *
 * 输入：s = "cbacdcbc"
 * 输出："acdb"
 *
 * @author hanjuntao
 * @date 2025/7/11 0011
 */
public class UL_316_remove_duplicate_letters {

    public static void main(String[] args) {
        String s = "bcabc";
        System.out.println(removeDuplicateLetters(s));

        s = "cbacdcbc";
        System.out.println(removeDuplicateLetters(s));
    }

    /**
     * 思路：
     *
     *
     * @param s
     * @return
     */
    public static String removeDuplicateLetters(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        // 统计每个字符出现的次数
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }

        // 存放去重的结果
        Stack<Character> stk = new Stack<>();
        // 布尔数组初始值为 false，记录栈中是否存在某个字符
        // 输入字符均为 ASCII 字符，所以大小 256 够用了
        boolean[] inStack = new boolean[256];

        for (char c : s.toCharArray()) {
            // 如果字符 c 存在栈中，直接跳过
            if (inStack[c]) {
                continue;
            }

            // 栈顶元素大于 c，则弹出栈顶元素
            while (!stk.empty() && stk.peek() > c) {
                if (count.getOrDefault(stk.peek(), 0) == 0) {
                    break;
                }
                char top = stk.pop();
                inStack[top] = false;
            }
            // 若不存在，则插入栈顶并标记为存在
            stk.push(c);
            inStack[c] = true;
            count.put(c, count.getOrDefault(c, 0) - 1);
        }

        StringBuilder sb = new StringBuilder();
        while (!stk.empty()) {
            sb.append(stk.pop());
        }
        // 栈中元素插入顺序是反的，需要 reverse 一下
        return sb.reverse().toString();
    }
}
